package LeetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LC_140_WordBreakII {
    public static void main(String[] args) {

    }

    public class Solution {
        private void solve(List<String> res, String s, String cur, List<String> wordDict) {
            if (s.length() <= 0) {
                res.add(cur);
                return;
            }
            for (String str : wordDict) {
                int len = str.length();
                if (len <= s.length() && s.substring(0, len).equals(str)) {
                    solve(res, s.substring(len), cur.length() == 0 ? str : cur + " " + str, wordDict);
                }
            }
        }

        public List<String> wordBreak(String s, List<String> wordDict) {
            List<String> res = new LinkedList<>();
            if (!isWordBreak(s, wordDict))
                return res;

            solve(res, s, "", wordDict);
            return res;
        }

        private boolean isWordBreak(String s, List<String> wordDict) {
            int length = s.length();
            boolean[] words = new boolean[length];

            for (int i = 1; i <= length; i++) {
                int j;
                for (j = 0; j < i; j++) {
                    String substr = s.substring(j, i);
                    if (wordDict.contains(substr) && (j == 0 || words[j - 1])) {
                        words[i - 1] = true;
                        break;
                    }
                }
                if (j == i)
                    words[i - 1] = false;
            }
            return words[length - 1];
        }
    }

    static class Solution_2 {
        private void solve(List<String> res, String s, String cur, List<String> wordDict) {
            if (s.length() <= 0) {
                res.add(cur);
                return;
            }
            for (String str : wordDict) {
                int len = str.length();
                if (len <= s.length() && s.substring(0, len).equals(str)) {
                    solve(res, s.substring(len), cur.length() == 0 ? str : cur + " " + str, wordDict);
                }
            }
        }

        public List<String> wordBreak(String s, List<String> wordDict) {
            List<String> res = new LinkedList<>();

            solve(res, s, "", wordDict);
            return res;
        }
    }

    static class Solution_3 {
        public List<String> wordBreak(String s, List<String> wordDict) {
            List<List<String>> dpArray = new ArrayList<>();

            for (int i = 1; i <= s.length(); i++) {
                dpArray.add(new LinkedList<>());
                for (int j = 0; j < i; j++) {
                    String substr = s.substring(j, i);
                    if (wordDict.contains(substr)) {
                        if (j == 0) {
                            dpArray.get(i - 1).add(substr);
                        } else if (dpArray.get(j - 1).size() > 0) {
                            List<String> prevList = dpArray.get(j - 1);
                            int size = prevList.size();
                            List<String> tmp = dpArray.get(i - 1);
                            for (String aPrevList : prevList) {
                                tmp.add(aPrevList + " " + substr);
                            }
                        }
                    }
                }
            }
            return dpArray.get(s.length() - 1);
        }
    }
}
